---
title: "Bronze Lilypad Pond B"
created: 2025-11-28
tags:
  - 算法
---

# Bronze Lilypad Pond B

## 题目 [Bronze Lilypad Pond B](https://www.luogu.com.cn/problem/P2385)

![[image-8f92721e.png]]

## 思路分析

![[image-07d514b6.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=35;

int g[N][N],d[N][N];

int n,m;

int startx,starty;

int targetx,targety;

int* dx;

int* dy;

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1;

}

int bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	q.push({x,y});

	d[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<8;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && (g[nx][ny]==1 || g[nx][ny]==4)){

				d[nx][ny]=d[ux][uy]+1;

				q.push({nx,ny});

			}

		}

	}

	return d[targetx][targety];

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int	M1,M2;

	cin>>n>>m>>M1>>M2;

	int tempx[8]={-M1,-M2,M2,M1,M1,M2,-M2,-M1};

	dx=tempx;

	int tempy[8]={M2,M1,M1,M2,-M2,-M1,-M1,-M2};

	dy=tempy;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			cin>>g[i][j];

			if(g[i][j]==3)

				startx=i,starty=j;

			if(g[i][j]==4)

				targetx=i,targety=j;

		}

	}

	cout<<bfs(startx,starty)<<endl;

	return 0;

 }
```

试验了一下 这样也是可以的

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=35;

int g[N][N],d[N][N];

int n,m;

int startx,starty;

int targetx,targety;

int* dx;

int* dy;

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1;

}

int bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	q.push({x,y});

	d[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

        //取出来的是终点 说明可以结束了

		if(ux==targetx && uy==targety)

		    return d[targetx][targety];

		for(int i=0;i<8;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && (g[nx][ny]==1 || g[nx][ny]==4)){

				d[nx][ny]=d[ux][uy]+1;

				q.push({nx,ny});

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int	M1,M2;

	cin>>n>>m>>M1>>M2;

	int tempx[8]={-M1,-M2,M2,M1,M1,M2,-M2,-M1};

	dx=tempx;

	int tempy[8]={M2,M1,M1,M2,-M2,-M1,-M1,-M2};

	dy=tempy;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			cin>>g[i][j];

			if(g[i][j]==3)

				startx=i,starty=j;

			if(g[i][j]==4)

				targetx=i,targety=j;

		}

	}

	cout<<bfs(startx,starty)<<endl;

	return 0;

 }
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/BFS/迷宫问题（最短路）/5、迷宫|5、迷宫]] 🏠 [[00-刷题理模型]] ➡️ [[Mzc和男家丁的游戏|Mzc和男家丁的游戏]]